package Z.dailyExercise.May;

public class _105从前序与中序遍历序列构造二叉树 {

    /**
     * 查找根节点位置 然后划分左右子树 进行递归
     * 递归函数返回的是根节点
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder,inorder,0,preorder.length,0,inorder.length);



    }
    public TreeNode helper(int[] pre,int[] in,int p_l,int p_r,int i_l,int i_r){
        if (p_l == p_r){
            return null;
        }
        int root_val = pre[p_l];
        TreeNode root = new TreeNode(root_val);

        //前序遍历中找root
        int root_index=0;
        for (int i = i_l; i < i_r; i++) {
            if (in[i] == root_val){
                root_index = i;
                break;
            }

        }
        int leftnum = root_index-i_l;
        root.left = helper(pre,in,p_l+1,p_l+leftnum+1,i_l,root_index);
        root.right = helper(pre,in,p_l+leftnum+1,p_r,root_index+1,i_r);

        return root;
    }
}
